package TenkindsOfAlgorithm.greedyAlgorithm;

import java.util.Arrays;


public class severalGreedyQA {
    public static void main(String[] args) {
      int  timeSheet[][] =new int[][] {
              {1,4},{3,5},{0,6},{4,7},{3,8},{5,9},{6,10},{8,11}
        };
      int weight[] = new int[]{
              5,1,8,4,6,3,2,4
      };
      int stock[] = new int[]{
              1,2,9,10
      };
      int i = 0;
        for (int[] ints : timeSheet) {
            System.out.println((i++)+" "+Arrays.toString(ints));
        }
        System.out.println(rect(timeSheet, timeSheet.length - 1,weight));
        System.out.println(eraseOverlap(timeSheet));
        System.out.println(solution(stock));
    }

    /**
     * /**
     * 一群孩子吃饼干 孩子有饥饿数，饼干有对应能量 这群孩子最多能吃多少块
     * input : 1 2 3
     * 1 2
     * output : 2
     */
    static int cookie(int[] children, int[] cookies) {
        Arrays.sort(children);
        Arrays.sort(cookies);
        int i = 0, j = 0;  // 定义为孩子与饼干的下标
        while (i < children.length && j < cookies.length) {
            if (children[i] >= cookies[j++]) {
                i++;
            }
        }
        return i;
    }

    /**
     * 区间问题 给定多个区间，计算让这些区间互补重叠所需要移除区间的最小个数。
     * 变种：给老板安排更过的会议，而这些会议会有冲突
     * input :[[1,2],[2,4],[1,3]]
     * output:1
     * 这里我们采用贪婪算法 区间的结尾每次选最小的（但为什么选最小的）
     */
    static int eraseOverlap(int[][] intervals) {
        Arrays.sort(intervals, (o1, o2) -> {
            return o1[1] - o2[1];
        });
        int count = 1; // 满足条件的区间个数
        int pre = intervals[0][1];
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] >= pre) {
                count++;
                pre = intervals[i][1];
            }
        }
        return intervals.length-count;
    }
    /**
     * 使用dp 求最优解 时刻牢记i表示前i个的最优解包含i
     * 这里使用了01 背包 权重可以全部设为1，那么意思为个数
     * 牢记：我求i的最优解，i有选与不选。我取个Max就好了
     */
   // 历时将尽一小时终于哇
    static int rect(int[][] intervals,int i,int []weight){
        if (i==-1){
            return 0;
        }else if (i==0){
            return weight[0];
        }
        else {
            int pre = -1;
            for (int j = i-1; j >=0 ; j--) {
                if (intervals[i][0]>=intervals[j][1]){
                    pre = j;
                    break;
                }
            }
            int A = rect(intervals,pre,weight)+weight[i];
            int B = rect(intervals,i-1,weight);
            return Math.max(A,B);
        }
    }
    /**
     * 给定一个数组，他的第i个元素是一支给定股票第i天的价格
     * 设计一个算法来计算你所能获取的最大利润。你可以尽可能完成多的交易
     * input : [7,1,5,3,6,2]
     * output :7
     * 贪心的点在于：今天买明天。但是可以同一天买卖。
     */
    static int solution(int []prices){
        int profit = 0;
        for (int i = 0; i < prices.length-1; i++) {
            if(prices[i]<prices[i+1]){
                profit+=prices[i+1]-prices[i];
            }
        }
        return profit;
    }

}
